package queue;
//496. 下一个更大元素 I

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 单调栈
 */
public class Num496_NextGreaterNum {

    //单调栈
    private Stack<Integer> stack = new Stack<>();
    //存储nums2中的每个元素，一节下一个更大元素
    private Map<Integer,Integer> map = new HashMap<>();
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //1.扫描nums2，维护单调栈
        //倒着向前遍历是为了正向解决问题
        for (int i = nums2.length-1; i > -1; i--) {
            while (!stack.isEmpty()&&stack.peek()<=nums2[i]){
                stack.pop();
            }
            int nextGreatervalue = stack.isEmpty()?-1:stack.peek();
            //处理完当前元素后，将当前元素压入栈，因为当前元素
            stack.push(nums2[i]);
            map.put(nums2[i],nextGreatervalue);
        }
        //再次扫描nums1，取出每个元素对应的value就是结果集
        int []ret = new int[nums1.length];
        for (int i = 0; i < ret.length; i++) {
            ret[i]=map.get(nums1[i]);
        }
        return ret;
    }
}
